package com.Offer;

/*
    面试题39：数组中出现次数超过一半的数字
    题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数 字。如果不存在则输出 0。
 */
public class demo39 {
    public static void main(String[] args) {
        int[] input = {1,2,3,4,5,5,5,5,5,5,6,6,6,6,5,5,5};
        System.out.println(moreThanHalfNum(input));
        System.out.println(moreThanHalfNum2(input));
    }

    //方法一，基于快速排序的Partition函数的时间复杂度为0n的算法
    public static int moreThanHalfNum(int[] input){
        if(input == null || input.length == 0){
            return 0;
        }
        int temp = Position(input,0,input.length-1);
        int mid = input.length/2;
        while(temp != mid){
            if(temp > mid){
                temp = Position(input,0,temp-1);
            }else if(temp < mid){
                temp = Position(input,temp+1,input.length-1);
            }
        }
        if(CheckMoreThanHalf(input,input[temp])){
            return input[temp];
        }else{
            return 0;
        }
    }

    public static boolean CheckMoreThanHalf(int[] input,int number){
        int times = 0;
        for(int i : input){
            if(i == number){
                times++;
            }
        }
        return times*2 >= input.length;
    }

    public static int Position(int[] input,int start,int end){
        int temp = input[start];
        while(start < end){
            while(start < end && input[end] >= temp){
                end--;
            }
            input[start] = input[end];
            while(start < end && input[start] <= temp){
                start++;
            }
            input[end] = input[start];
        }
        input[start] = temp;
        return start;
    }

    //-------------------------------------------------------------------

    //方法二，基于数组特性，利用其它元素的个数合 不超过 最多的元素的个数 的特性来进行获取超过一半数组的元素
    public static int moreThanHalfNum2(int[] nums){
        int count = 0;
        int candidate = 0;  //保存当前元素的值，最后也是通过这个值来得到超过一半个数的元素值
        for(int num: nums){
            if (count == 0){
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        return checkMoreThanHalf(nums,candidate) ? candidate : 0;
    }

    public static boolean checkMoreThanHalf(int[] array,Integer number){
        int times = 0;
        for(int i : array){
            if(i == number){
                times++;
            }
        }
        return times*2 >= array.length;
    }

}
